import MapModel from "./MapModel";

export default class AStar {

    private static instance: AStar = null;

    public static getInstance(): AStar {
        if (this.instance == null) {
            this.instance = new AStar();
        }
        return this.instance;
    }

    //能否斜着走
    private OBLIQUE_ABLE = true;

    //走直线和走斜线的权重，用整数计算比小数更快
    private readonly STRAIGHT_COST = 10;
    private readonly OBLIQUE_COST = 14;

    //地图数据
    get mapData() {
        //地图数据来源
        let data = MapModel.mapData;

        // [
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        // ];
        return data;
    }

    //某个格子是否能通过
    private walkAble(mapPoint: { x, y }) {
        let horzionLen = this.mapData.length;
        let vertical = this.mapData[0].length;

        if (mapPoint.x < 0 || mapPoint.x >= horzionLen || mapPoint.y < 0 || mapPoint.y >= vertical) return false;

        return this.mapData[mapPoint.x][mapPoint.y] == 0;
    }

    //如果包含，返回索引，不包含，返回-1
    private isIncludeInList(list, point) {
        for (let i in list) {
            let p = list[i];
            if (p.x == point.x && p.y == point.y) {
                return parseInt(i);
            }
        }
        return -1;
    }

    //获取该点周围可走的点
    private getRoundGridOfWalkAble(mapPoint: { x, y }, openList, closeList, endPoint) {
        let girdList = [];

        let properList = [];

        //第一个 左上角
        let point = { x: mapPoint.x - 1, y: mapPoint.y - 1 }
        if (this.OBLIQUE_ABLE && this.walkAble(point)) {
            properList.push(point);
        }
        //第二个 上角
        point = { x: mapPoint.x - 1, y: mapPoint.y }
        if (this.walkAble(point)) {
            properList.push(point);
        }
        //第三个 右上角
        point = { x: mapPoint.x - 1, y: mapPoint.y + 1 }
        if (this.OBLIQUE_ABLE && this.walkAble(point)) {
            properList.push(point);
        }
        //第四个 左角
        point = { x: mapPoint.x, y: mapPoint.y - 1 }
        if (this.walkAble(point)) {
            properList.push(point);
        }
        //第五个 右角
        point = { x: mapPoint.x, y: mapPoint.y + 1 }
        if (this.walkAble(point)) {
            properList.push(point);
        }
        //第六个 左下角
        point = { x: mapPoint.x + 1, y: mapPoint.y - 1 }
        if (this.OBLIQUE_ABLE && point.y >= 0 && this.walkAble(point)) {
            properList.push(point);
        }
        //第七个 下角
        point = { x: mapPoint.x + 1, y: mapPoint.y }
        if (this.walkAble(point)) {
            properList.push(point);
        }
        //第八个 右下角
        point = { x: mapPoint.x + 1, y: mapPoint.y + 1 }
        if (this.OBLIQUE_ABLE && this.walkAble(point)) {
            properList.push(point);
        }

        for (let i in properList) {
            let p = properList[i];


            //如果已经包含了,则要比较是否为更优点
            let openIncludeIndex = this.isIncludeInList(openList, p)
            if (openIncludeIndex != -1) {
                let G1 = openList[openIncludeIndex]["G"];
                let G2 = mapPoint["G"] + this.getG(mapPoint, p);
                if (G2 < G1) {
                    //更优，更优
                    this.setF(mapPoint, p, endPoint);
                }
            }
            //如果openList里面没有，并且closeList里面没有，则纳入
            else {
                if (this.isIncludeInList(closeList, p) == -1) {
                    this.setF(mapPoint, p, endPoint);
                    girdList.push(p);
                }
            }

        }

        return girdList;
    }

    //获取G值：从起点 A 移动到指定方格的移动代价
    private getG(mapPoint, targetPoint) {
        let G = 0;
        //直线方向
        if (mapPoint.x == targetPoint.x || mapPoint.y == targetPoint.y) {
            G = this.STRAIGHT_COST;
        }
        //斜线方向
        else {
            G = this.OBLIQUE_COST;
        }
        return G;
    }

    //使用曼哈顿算法计算H值：从指定的方格移动到终点 End 的估算成本
    private getH(mapPoint, endPoint) {
        let H = 0;
        let Horizon = Math.abs(endPoint.x - mapPoint.x);
        let Vertical = Math.abs(endPoint.y - mapPoint.y);
        H = (Horizon + Vertical) * this.STRAIGHT_COST;
        return H;
    }

    //获取F值
    private setF(mapPoint, targetPoint, endPoint) {
        let F = 0;
        let G = this.getG(mapPoint, targetPoint);
        let H = this.getH(targetPoint, endPoint);
        F = G + H;
        targetPoint.G = G;
        targetPoint.H = H;
        targetPoint.F = F;
        targetPoint.parent = mapPoint;
    }

    //从列表里面获取最小的F值
    private getMinF(list) {
        let min = 100000000;
        let index = null;

        if (list.length == 1) {
            return list[0]
        }

        for (let i in list) {
            let f = list[i].F;
            if (f < min) {
                min = f;
                index = i;
            }
        }
        return list[index];
    }

    //删除指定的点
    private splicePoint(list, point: { x, y }) {
        for (let i in list) {
            if (list[i].x == point.x && list[i].y == point.y) {
                let result = list.splice(i, 1)
                return result[0];
            }
        }
    }

    //寻路
    public findPath(star: { x, y }, end: { x, y }, callback: Function = null) {
        //初始
        let openList = [star];
        let closeList = [];

        let calculateCount = 0;             //分帧去寻路，避免寻路时间过长卡顿
        let allCount = 0;
        let findNext = () => {
            allCount++;
            calculateCount++;

            let resultIndex = this.isIncludeInList(openList, end)
            if (resultIndex >= 0) {

                let path = [];
                let endPoint = openList[resultIndex];
                path.push(endPoint);

                let getParent = (point) => {
                    let parent = point.parent;
                    if (parent) {
                        path.push(parent);
                        getParent(parent);
                    } else {
                        callback(path);
                    }
                }
                getParent(endPoint);
                return;
            }
            if (openList.length == 0) {
                console.log("没有找到,查找了次数", allCount);
                return;
            }

            //--------------------------------------------------------------------------------
            let minF = this.getMinF(openList);
            closeList.push(minF);
            this.splicePoint(openList, minF);

            let round = this.getRoundGridOfWalkAble(minF, openList, closeList, end);
            openList = openList.concat(round);

            //---------------------------------------------------------------------------------

            //如果当前帧递归了n次，就换下一帧去递归
            if (calculateCount < 1000) {
                findNext();
            } else {
                setTimeout(() => {
                    calculateCount = 0;
                    findNext();
                })
            }
        }

        findNext();

    }

}
